This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
A fault attack disturbs the expected behaviour of a security device and makes it work abnormally so as to infer sensitive data from the faulty output. Such attacks were introduced by Boneh et al. in “On the Importance of Checking Cryptographic Protocols for Faults”; D. Boneh, R. A. DeMillo, and R. J. Lipton; In W. Fumy, editor, Advances in Cryptology—EUROCRYPT '97, volume 1233 of Lecture Notes in Computer Science, pages 37-51, Springer-Verlag 1997.
Fault attacks can be very powerful. For example, a faulty RSA signature with a single random fault and evaluated using Chinese remaindering (CRT) can allow an attacker to recover the entire secret key from the faulty signature. It is thus clear that countermeasures must be taken.
RSA is based on the fact that it is difficult to factorize products of large primes. Let N=pq be the product of two large primes. We let e and d denote a pair of matching public and private exponents, satisfying ed≡1 (mod λ(N)), with gcd(e, λ(N))=1 and λ being Carmichael's function. As N=pq, we have λ(N)=lcm(p−1, q−1). Given x<N, the public operation (e.g., message encryption or signature verification) consists in raising x to the e-th power modulo N, i.e., in computing y=xe mod N. Then, given y, the corresponding private operation (e.g., decryption of a ciphertext or signature generation) consists in computing yd mod N. From the definition of e and d, we obviously have that yd≡x (mod N). The private operation can be carried out at higher speed through Chinese remaindering (CRT mode). Computations are independently performed modulo p and q and then recombined. In this case, private parameters are {p, q, dp, dq, iq} with dp=d mod (p−1), dq=d mod (q−1), and iq=q−1 mod p. We then obtain yd mod N as CRT(xp, xq)=xq+q[iq(xp−xq) mod p], where xp=ydp mod p and xq=ydq mod q.
Naturally, several such countermeasures have been proposed. The initial countermeasure by Shamir is disclosed in U.S. Pat. No. 5,991,415, initially presented at the Rump Session of EUROCRYPT '97. Somewhat simplified, this method introduces a random value j and calculates using (mod j*p) instead of (mod p) and verifies that the expected value is arrived at; as a given example, if j is 32 bits long, the chance of the two values matching after a fault is 2−32=1/4,294,967,296, so the risk is very slight. More specifically, the values of x′p=yd mod j*p and xj=yd mod j are first calculated. It is verified that x′p≡xj (mod j) and if so, the calculation is assumed to be error-free. The result of the exponentiation modulo p is then given by xp=x′p mod p. This same is done modulo q. The correctness of the countermeasure relies on the observation that x mod p=(x mod j*p) mod p for any positive integer j.
Another method, mentioned by Kaliski and Robshaw in ftp://ftp.rsasecurity.com/pub/pdfs/bulletn5.pdf, consists in performing the exponentiation in a usual manner to obtain x=yd mod N, but, before issuing x, checking it is correct by checking that xe is equal to y modulo N.
All subsequent methods basically rely on the method proposed by Shamir. These methods include:                M. Joye, P. Paillier, and S-M. Yen. Secure Evaluation of Modular Functions. In R. J. Hwang and C. K. Wu, editors, 2001 International Workshop of Cryptology and Network Security, pages 227-229, Taipei, Taiwan, 2001.        C. Aumüler, P. Bier, W. Fischer, P. Hofreiter, and J-P. Seifert. Fault Attack on RSA with CRT: Concrete Results and Practical Countermeasures. In B. S. Kaliski Jr., C. K. Koç and C. Paar, editors, Cryptographic Hardware and Embedded Systems—CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages 260-275, Springer, 2002.        J. Blömer, M. Otto, and J-P. Seifert. A New CRT-RSA Algorithm Secure Against Bellcore Attack. In 10th ACM Conference on Computer and Communication Security (CCS 2003), pages 311-320, ACM Press, 2003.        M. Ciet and M. Joye. Practical Fault Countermeasures for Chinese Remaindering Based RSA. In 2nd Workshop Fault Diagnosis and Tolerance in Cryptography—FDTC 2005), pages 124-132, 2005.        C. H. Kim and J.-J. Quisquater. How Can We Overcome Both Side Channel Analysis and Fault Attacks on RSA-CRT? In 4th Workshop on Fault Diagnosis and Tolerance in Cryptography—FDTC 2007, pages 21-29, IEEE Computer Society Press, 2007.        
Of these, it has been shown that the methods of Blömer et al. and Ciet et al. do not offer full tamper-resistance. Furthermore, none of these methods guarantee a 100% detection of faults, and they all impact performance (running time and memory requirements) and, in some cases, the personalization process.
It will therefore be appreciated that there is a need for a countermeasure against fault attacks on RSA that detects all faults. This invention provides such a solution.